583. 两个字符串的删除操作

Solution Tips

方案一: LCS 换皮

var minDistance = function(word1, word2) {
    // 感觉还是 LCS, 先求出2个字符串的LCS, 然后部署就是直接删除即可
    const len1 = word1.length;
    const len2 = word2.length;
    // 1. dp[i][j] 表示以第 i 个字符结尾的 word1 子序列 和 以第 j 个字符结尾的 word2 子序列的 LCS 长度
    const dp = Array.from({ length: len1 + 1 }, () => Array.from({ length: len2 + 1 }, () => 0));

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    const lcs = dp[len1][len2];

    return len1 - lcs + len2 - lcs;
};

方案二: 编辑距离削弱版本

不求 LCS, 而是真正的执行删除, 联系一下 115. 不同的子序列, 这次是删除的情况稍微复杂一点

这次是两个字符串可以相互删了，这种题目也知道用动态规划的思路来解，动规五部曲，分析如下：

确定 Dp 数组（dp table）以及下标的含义

dp[i][j]：以 i-1 为结尾的字符串 word1，和以 j-1 位结尾的字符串 word2，想要达到相等，所需要删除元素的最少次数。

这里 dp 数组的定义有点点绕，大家要撸清思路。

确定递推公式

当 word1[i - 1] 与 word2[j - 1] 相同的时候，dp[i][j] = dp[i - 1][j - 1];

当 word1[i - 1] 与 word2[j - 1] 不相同的时候，有三种情况：

情况一：删 word1[i - 1]，最少操作次数为 dp[i - 1][j] + 1
情况二：删 word2[j - 1]，最少操作次数为 dp[i][j - 1] + 1
情况三：同时删 word1[i - 1] 和 word2[j - 1]，操作的最少次数为 dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当 word1[i - 1] 与 word2[j - 1] 不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

这里可能不少录友有点迷糊，从字面上理解就是当同时删 word1[i - 1] 和 word2[j - 1]，dp[i][j-1] 本来就不考虑 word2[j - 1] 了，那么我在删 word1[i - 1]，是不是就达到两个元素都删除的效果，即 dp[i][j-1] = dp[i-1][j-1] + 1

var minDistance = function(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = j;
    }
    for (let i = 1; i <= m; i++) {
        const c1 = word1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = word2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    return dp[m][n];
};